package com.sheng.leetcode.year2023.month10.day31;

import org.junit.Test;

import java.util.*;

/**
 * @author by ls
 * @date 2023/10/31
 * <p>
 * 2003. 每棵子树内缺失的最小基因值<p>
 * <p>
 * 有一棵根节点为 0 的 家族树 ，总共包含 n 个节点，节点编号为 0 到 n - 1 。<p>
 * 给你一个下标从 0 开始的整数数组 parents ，其中 parents[i] 是节点 i 的父节点。由于节点 0 是 根 ，所以 parents[0] == -1 。<p>
 * 总共有 10^5 个基因值，每个基因值都用 闭区间 [1, 10^5] 中的一个整数表示。<p>
 * 给你一个下标从 0 开始的整数数组 nums ，其中 nums[i] 是节点 i 的基因值，且基因值 互不相同 。<p>
 * 请你返回一个数组 ans ，长度为 n ，其中 ans[i] 是以节点 i 为根的子树内 缺失 的 最小 基因值。<p>
 * 节点 x 为根的 子树 包含节点 x 和它所有的 后代 节点。<p>
 * <p>
 * 示例 1：<p>
 * 输入：parents = [-1,0,0,2], nums = [1,2,3,4]<p>
 * 输出：[5,1,1,1]<p>
 * 解释：每个子树答案计算结果如下：<p>
 * - 0：子树包含节点 [0,1,2,3] ，基因值分别为 [1,2,3,4] 。5 是缺失的最小基因值。<p>
 * - 1：子树只包含节点 1 ，基因值为 2 。1 是缺失的最小基因值。<p>
 * - 2：子树包含节点 [2,3] ，基因值分别为 [3,4] 。1 是缺失的最小基因值。<p>
 * - 3：子树只包含节点 3 ，基因值为 4 。1是缺失的最小基因值。<p>
 * <p>
 * 示例 2：<p>
 * 输入：parents = [-1,0,1,0,3,3], nums = [5,4,6,2,1,3]<p>
 * 输出：[7,1,1,4,2,1]<p>
 * 解释：每个子树答案计算结果如下：<p>
 * - 0：子树内包含节点 [0,1,2,3,4,5] ，基因值分别为 [5,4,6,2,1,3] 。7 是缺失的最小基因值。<p>
 * - 1：子树内包含节点 [1,2] ，基因值分别为 [4,6] 。 1 是缺失的最小基因值。<p>
 * - 2：子树内只包含节点 2 ，基因值为 6 。1 是缺失的最小基因值。<p>
 * - 3：子树内包含节点 [3,4,5] ，基因值分别为 [2,1,3] 。4 是缺失的最小基因值。<p>
 * - 4：子树内只包含节点 4 ，基因值为 1 。2 是缺失的最小基因值。<p>
 * - 5：子树内只包含节点 5 ，基因值为 3 。1 是缺失的最小基因值。<p>
 * <p>
 * 示例 3：<p>
 * 输入：parents = [-1,2,3,0,2,4,1], nums = [2,3,4,5,6,7,8]<p>
 * 输出：[1,1,1,1,1,1,1]<p>
 * 解释：所有子树都缺失基因值 1 。<p>
 * <p>
 * 提示：<p>
 * n == parents.length == nums.length<p>
 * 2 <= n <= 10^5<p>
 * 对于 i != 0 ，满足 0 <= parents[i] <= n - 1<p>
 * parents[0] == -1<p>
 * parents 表示一棵合法的树。<p>
 * 1 <= nums[i] <= 10^5<p>
 * nums[i] 互不相同。<p>
 */
public class LeetCode2003 {

    @Test
    public void test01() {
//        int[] parents = {-1, 0, 0, 2}, nums = {1, 2, 3, 4};
//        int[] parents = {-1, 0, 1, 0, 3, 3}, nums = {5, 4, 6, 2, 1, 3};
        int[] parents = {-1, 2, 3, 0, 2, 4, 1}, nums = {2, 3, 4, 5, 6, 7, 8};
        System.out.println(Arrays.toString(new Solution().smallestMissingValueSubtree(parents, nums)));
    }
}

class Solution {
    // 考虑到有不懂「链式前向星」的同学, 这里使用最简单的存图方式 {1: [2, 3]} 代表节点 1 有两个子节点 2 和 3
    Map<Integer, List<Integer>> g = new HashMap<>();

    public int[] smallestMissingValueSubtree(int[] parents, int[] nums) {
        int n = nums.length, cur = -1;
        int[] ans = new int[n];
        Arrays.fill(ans, 1);
        // 找节点 1, 建图
        for (int i = 0; i < n; i++) {
            if (nums[i] == 1) cur = i;
            List<Integer> list = g.getOrDefault(parents[i], new ArrayList<>());
            list.add(i);
            g.put(parents[i], list);
        }

        // 若 nums 中没 1, 对应结论一
        if (cur == -1) return ans;

        boolean[] vis = new boolean[100010];
        // 从节点 1 开始往根找（从深到浅）, idx 代表当前节点, ne 代表 cur 在该链路下的子节点
        int ne = cur, val = 1;
        while (cur != -1) {
            // 每次对当前节点所在子树的进行标记
            dfs(cur, ne, nums, vis);
            // 在 [val, n+1] 范围内找第一个未被标记基因值
            for (int i = val; i <= n + 1; i++) {
                if (vis[i]) continue;
                ans[cur] = val = i;
                break;
            }
            ne = cur;
            cur = parents[cur]; // 指针上移
        }
        return ans;
    }

    void dfs(int idx, int block, int[] nums, boolean[] vis) {
        vis[nums[idx]] = true;
        List<Integer> list = g.getOrDefault(idx, new ArrayList<>());
        for (int x : list) {
            if (x == block) continue;
            dfs(x, block, nums, vis);
        }
    }
}
